package top.fengleifeng.question;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import top.fengleifeng.util.Constants;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2020年11月25日 11:54 上午
 */
public class Num869重新排序得到2的幂 {
    //传统思路 会超时
//    class Solution {
//
//        public boolean reorderedPowerOf2(int N) {
//            String s = N + "";
//            char[] chars = s.toCharArray();
//            LinkedList<String> all = getList(chars);
//            for (int i = 0; i < all.size(); i++) {
//                String ss = all.get(i);
//                boolean check = check(ss);
//                if (check) {
//                    return true;
//                }
//            }
//            return false;
//        }
//
//        private boolean check(String ss) {
//            Long n = Long.parseLong(ss);
//            Long l = n & (n - 1);
//            if (l == 0) {
//                return true;
//            }
//            return false;
//        }
//
//        public LinkedList<String> getList(char[] chars) {
//            StringBuffer sb = new StringBuffer("");
//            LinkedList<String> all = new LinkedList<>();
//            boolean[] haveUsed = new boolean[chars.length];
//            getkkkk(sb, all, haveUsed, chars);
//            Constants.pringLinkedListStr(all);
//            System.out.println();
//            return all;
//        }
//
//        public void getkkkk(StringBuffer sb, LinkedList<String> all, boolean[] haveUsed, char[] chars) {
//            if (sb.length() == chars.length) {
//                String ss = sb.toString();
//                if (!all.contains(ss) && !ss.startsWith("0")) {
//                    all.add(new String(sb.toString()));
//                }
//                return;
//            }
//            for (int i = 0; i < chars.length; i++) {
//                if (haveUsed[i]) {
//                    continue;
//                }
//                sb.append(chars[i]);
//                haveUsed[i] = true;
//                getkkkk(sb, all, haveUsed, chars);
//                sb.deleteCharAt(sb.length() - 1);
//                haveUsed[i] = false;
//            }
//        }
//    }

    //将数字排序 和该数字数量相等的2的数量进行比较计算
    class Solution {

        public boolean reorderedPowerOf2(int N) {
            if (N <= 0) {
                return false;
            }
            String str = N + "";
            int strLength = str.length();
            List<String> list = new LinkedList<>();
            for (int i = 0; i < Integer.MAX_VALUE; i++) {
                Double d = Math.pow(2, i);
                Long l = d.longValue();
                String sss = l + "";
                if (sss.length() < strLength) {
                    continue;
                } else if (sss.length() == strLength) {
                    list.add(sss);
                } else {
                    break;
                }
            }
            char[] now = str.toCharArray();
            Arrays.sort(now);
            str = new String(now);
            for (int i = 0; i < list.size(); i++) {
                String one = list.get(i);
                char[] oneChar = one.toCharArray();
                Arrays.sort(oneChar);
                one =  new String(oneChar);
                if(one.equals(str)){
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        int n = 10;
        boolean b = new Num869重新排序得到2的幂().new Solution().reorderedPowerOf2(n);
        System.out.println(b);
//        System.out.println();
//        int k = 5 % 2;
//        System.out.println(k);
    }
}
